package com.promote.algorithm;

import java.util.PriorityQueue;

import static java.util.Arrays.sort;

/**
 * @ClassName FindKthLargest
 * Description 数组中的第K个最大的元素
 * @Author LiZiHao
 * Date 2023/2/25 10:30
 * @Version 1.0
 **/
public class FindKthLargest {

    //暴力解法
    public int findKthLargest(int[] nums, int k) {
        sort(nums);
        return nums[nums.length - k];
    }
    //基于堆排序,建立最小根堆

    public int findKthLargest1(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.add(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        return pq.peek();
    }
    //快速排序方式
    public int findKthLargest2(int[] nums, int k) {
        return quickSort(nums,0,nums.length-1,k);
    }
    public int quickSort(int[] nums,int l,int r,int k) {
        int index = randomPartition(nums, l, r);
        if (index == k-1) {
            return nums[index];
        } else {
            return index > k-1 ? quickSort(nums,l,index-1,k):quickSort(nums,index+1,r,k);
        }
    }
    public int randomPartition(int[] nums, int l,int r) {
        int i = (int)(Math.random()*(r-1))+1;
        swap(nums,i,r);
        return partition(nums,l,r);
    }
    //交换函数
    public void swap(int[] nums,int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    //随机选择一个数，大的放左边，小的放右边
    public int partition(int[] nums, int l,int r) {
        int pivot = nums[r];
        int rightmost = r;
        while (l <= r) {
            while (l <= r && nums[l] > pivot) {
                l++;
            }
            while (l <= r && nums[r] <= pivot) {
                r --;
            }
            if (l <= r) {
                swap(nums,l,r);
            }
        }
        swap(nums,l,rightmost);
        return l;
    }
}
